package class_3;

import java.io.IOException;
import java.util.Random;

public class Coding_DecodeWays2 {
	public static int numDecodings(String s) {
		int n = s.length();
		int[] dp = new int[n+1];
		dp[n] = 1;
		char ch;
		for(int i = n-1;i>=0;i--) {
			ch = s.charAt(i);
			if(ch=='0') {
				dp[i] = 0;
			}
			else {
				dp[i] = dp[i+1];
				if(i+1<n && ((ch - '0') * 10 + s.charAt(i+1) - '0') <= 26) {
					dp[i] += dp[i+2];
				}
			}
		}
		return dp[0];
	}
	
	/**
	 * 再大胆一点， 自底向下依赖的过程能不能省空间。
	 * 可以想象成滚动数组。
	 * 这个是最省空间和时间的方案。 自底向上的迭代动态规划， 一维的方案标记好状态转移方程能够循环滚动就可以省空间。
	 * over!
	 */
	public static int numDecodings1(String s) {
		int n = s.length();
		int next = 1;
		int nextNext = 0;
		int cur = 0;//代表当前位置开始的解码方案数， 初始化为0考虑了空字符串的情况。
		char ch;
		for(int i = n-1;i>=0;i--) {
			ch = s.charAt(i);
			if(ch=='0') {
				cur = 0;
			}
			else {
				// ch !='0' 意味cur至少依赖下一个参数next
				cur = next;
				//尝试带着两个字母解码。
				//不越界和满足范围
				if(i+1<n && ((ch - '0') * 10 + s.charAt(i+1) - '0') <= 26) {
					cur += nextNext;//位置也依赖下一个参数nextNext。
				}
			}
			//数据滚动
			nextNext = next;
			next = cur;
		}
		return cur;//next也是相同的值
	}
	
	public static int MAX = 100;
	public static char[] ch = new char[MAX];
	public static void main(String[] args) throws IOException {
		Random random = new Random();
		int n = random.nextInt(MAX);
		for(int i=0;i<n;i++) {
			ch[i] = (char)(random.nextInt(10) + '0');
		}
		String s = new String(ch,0,n);
	     System.out.println("字符串长度: " + n);
		 // 为了避免打印过长的字符串，截断显示部分内容
        if (n > 50) {
            System.out.println("字符串: " + s.substring(0, 50) + "...");
        } else {
            System.out.println("字符串: " + s);
        }

        // 暴力递归方式计算解码方案
        long start = System.nanoTime();
        int ret = numDecodings(s);
        long end = System.nanoTime();
        System.out.println("解码方案数 (动态规划): " + ret);
        System.out.println("动态规划（位置依赖）耗时: " + (end - start) + " 纳秒");

        // 动态规划方式计算解码方案
        start = System.nanoTime();
        ret = numDecodings1(s);
        end = System.nanoTime();
        System.out.println("解码方案数 (动态规划): " + ret);
        System.out.println("动态规划（位置依赖+空间压缩）耗时: " + (end - start) + " 纳秒");
        System.out.println("-----------------");
		
		
	}
	
}
